package com.likou;

import java.util.*;

public class q347 {

    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();

        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        List<Integer> list = new ArrayList<>(map.values());

        heapSort(list, k);
        Set<Integer> values = new HashSet<>();
        for (int i = list.size() - k; i <= list.size() - 1; i++) {
            values.add(list.get(i));
        }
        int[] ans = new int[k];
        int m = 0;
        for (Integer key : map.keySet()) {
            if (values.contains(map.get(key))) {
                ans[m] = key;
                m++;
            }
        }

        return ans;
    }

    private void heapSort(List<Integer> list, int k) {
        int n = list.size();

        //  构建大根堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(list, n, i);
        }

        int mark = 0;
        for (int i = n - 1; i >= 1; i--) {
            Integer temp = list.get(i);
            list.set(i, list.get(0));
            list.set(0, temp);
            mark++;
            if (mark == k) {
                return;
            }

            heapify(list, i, 0);
        }

    }

    private void heapify(List<Integer> list, int n, int index) {
        int maxIndex = index;
        int left = 2 * index + 1;
        int right = 2 * index + 2;

        if (left < n && list.get(left) > list.get(maxIndex)) {
            maxIndex = left;
        }
        if (right < n && list.get(right) > list.get(maxIndex)) {
            maxIndex = right;
        }

        if (maxIndex != index) {
            Integer temp = list.get(index);
            list.set(index, list.get(maxIndex));
            list.set(maxIndex, temp);

            heapify(list, n - 1, maxIndex);
        }
    }
}
